#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<unordered_set>
using namespace std;


struct ListNode{
    int val;
    ListNode* next;
    ListNode(int x): val(x), next(nullptr){}
};

class Solution{
    public:

    pair<ListNode*, ListNode*> myReverse(ListNode* head, ListNode* tail) {
        ListNode* prev = tail->next;
        ListNode* p = head;
        while (prev != tail) {
            ListNode* nex = p->next;
            p->next = prev;
            prev = p;
            p = nex;
        }
        return {tail, head};
    }

    ListNode* ans1(ListNode* head, int left, int right){
        ListNode *dummyNode = new ListNode(-1);
        dummyNode->next = head;
        ListNode *pre = dummyNode;
        for (int i = 0; i < left - 1; i++) {
            pre = pre->next;
        }
        ListNode *cur = pre->next;
        ListNode *next;
        for (int i = 0; i < right - left; i++) {
            next = cur->next;
            cur->next = next->next;
            next->next = pre->next;
            pre->next = next;
        }
        return dummyNode->next;
    }


    ListNode* ans2(ListNode* head, int left, int right){
        ListNode *dummyNode = new ListNode(-1);
        dummyNode->next = head;
        ListNode* l = head;
        ListNode* r = head;
        ListNode* pre;
        for(int i = 0; i < left-1; i++){
            pre = l;
            l = l->next;
        }
        
        for(int i = 0; i < right-1; i++){
            r = r->next;
        }
        ListNode* nex = r->next;
        tie(l, r) = myReverse(l, r);
        pre->next = l;
        r->next = nex;
        
        return dummyNode->next;
    }

};

void test1(){
    vector<int> num = {1,2,3,4,5,6,7,8};
    ListNode* head = nullptr;
    ListNode* tail = nullptr;
    for(int i = 0; i != num.size(); i++){
        if(!head){
            head = tail = new ListNode(num[i]);
        }else{
            tail->next = new ListNode(num[i]);
            tail = tail->next;
        }
    }
    int left = 2, right = 6;

    Solution s;
    // ListNode* ret = s.ans1(head, left, right);
    ListNode* ret = s.ans2(head, left, right);
    while(ret){
        cout << ret->val << " " << ends;
        ret = ret->next;
    }
    cout << endl;
}

void test2(){
    vector<int> num = {3,5};
    ListNode* head = nullptr;
    ListNode* tail = nullptr;
    for(int i = 0; i != num.size(); i++){
        if(!head){
            head = tail = new ListNode(num[i]);
        }else{
            tail->next = new ListNode(num[i]);
            tail = tail->next;
        }
    }
    int left = 1, right = 1;

    Solution s;
    ListNode* ret = s.ans1(head, left, right);
    while(ret){
        cout << ret->val << " " << ends;
        ret = ret->next;
    }
    cout << endl;
}

void test3(){
    vector<int> num = {1,2,3};
    ListNode* head = nullptr;
    ListNode* tail = nullptr;
    for(int i = 0; i != num.size(); i++){
        if(!head){
            head = tail = new ListNode(num[i]);
        }else{
            tail->next = new ListNode(num[i]);
            tail = tail->next;
        }
    }
    int left = 1, right = 2;

    Solution s;
    ListNode* ret = s.ans1(head, left, right);
    while(ret){
        cout << ret->val << " " << ends;
        ret = ret->next;
    }
    cout << endl;
}

int main(void){
    test1();
    test2();
    test3();

    return 0;
}